﻿#include "邻接图.h"

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#include "栈.h"

邻接图* 构造_邻接图(const int 节点数)
{
    邻接图 *图 = malloc(sizeof(邻接图));
    图->节点数 = 节点数;
    图->节点表 = calloc(节点数,sizeof(int));
    图->邻接矩阵 = calloc(节点数,sizeof(int*));
    for (int i = 0;i<节点数;i++)
    {
        图->节点表[i] = 0;
        图->邻接矩阵[i] = calloc(节点数,sizeof(int));
        for (int j = 0;j<节点数;j++)
        {
            图->邻接矩阵[i][j] = 0;
        }
    }
    return 图;
}

void 设置图的节点值(const 邻接图 *图, const int 节点索引, const int 节点值)
{
    图->节点表[节点索引] = 节点值;
}

void 设置图的边(const 邻接图* 图, const int 从, const int 到, const int 权值)
{
    图->邻接矩阵[从][到] = 权值;
}

void 销毁_邻接图(邻接图* 图)
{
    free(图->节点表);
    for (int i = 0;i < 图->节点数;i++)
    {
        free(图->邻接矩阵[i]);
    }
    free(图);
}

void 邻接图广度优先遍历(const 邻接图* 图, const int 始,void (*执行函数)(int))
{
    const int 节点数 = 图->节点数;
    const int* 节点表 = 图->节点表;
    const int **邻接矩阵 = 图->邻接矩阵;
    执行函数(节点表[始]);
    bool *已访问 = calloc(节点数,sizeof(bool));
    bool *已使用 = calloc(节点数,sizeof(bool));
    
    for (int i = 0;i < 节点数;i++)
    {
        已访问[i] = false;
        已使用[i] = false;
    }
    已访问[始] = true;
    已使用[始] = true;
    
    bool 全部访问了;
    int 当前访问节点 = 始;
    do
    {
        const int *出度表 = (int*)邻接矩阵[当前访问节点];
        已使用[当前访问节点] = true;
        for(int i = 0;i < 节点数;i++)
        {
            if(出度表[i] > 0 && !已访问[i])
            {
                执行函数(节点表[i]);
                已访问[i] = true;
            }
        }
        for(int i = 0;i < 节点数;i++)
        {
            if(当前访问节点 != i && !已使用[i])
            {
                当前访问节点 = i;
                break;
            }
        }
        全部访问了 = true;
        for(int i = 0;i < 节点数;i++)
        {
            if(!已访问[i])
            {
                全部访问了 = false;
                break;
            }
        }
    }
    while (!全部访问了);
    
    free(已使用);
    free(已访问);
}

void 邻接图深度优先遍历(const 邻接图* 图, const int 始,void(* 执行函数)(int))
{
    const int 节点数 = 图->节点数;
    const int* 节点表 = 图->节点表;
    const int **邻接矩阵 = 图->邻接矩阵;
    执行函数(节点表[始]);
    bool *已访问 = calloc(节点数,sizeof(bool));
    for (int i = 0;i < 节点数;i++)
    {
        已访问[i] = false;
    }
    已访问[始] = true;
    
    bool 全部访问了;
    int 当前访问节点 = 始;
    栈_结构 *访问栈 = 构造_栈();
    bool 节点是否出栈 = false;
    do
    {
        切换节点访问:
        if(节点是否出栈 == true)
        {
            数据出栈(访问栈);
            当前访问节点 = 查看栈顶数据(访问栈);
        }
        const int *出度表 = (int*)邻接矩阵[当前访问节点];
        节点是否出栈 = true;
        for(int i = 0;i < 节点数;i++)
        {
            if(出度表[i] > 0 && !已访问[i])
            {
                已访问[i] = true;
                数据入栈(访问栈, i);
                执行函数(节点表[i]);
                当前访问节点 = i;
                节点是否出栈 = false;
                goto 切换节点访问;
            }
        }
        
        全部访问了 = true;
        for(int i = 0;i < 节点数;i++)
        {
            if(!已访问[i])
            {
                全部访问了 = false;
                break;
            }
        }
    }
    while (!全部访问了);
    销毁_栈(访问栈);
    free(已访问);
}

void 打印邻接图(const 邻接图* 图)
{
    const int* 顶点 = 图->节点表;
    const int **邻接矩阵 = 图->邻接矩阵;
    const int 顶点数 = 图->节点数;

    printf_s("图顶点：\n");
    
    for(int i = 0;i < 顶点数;i++)
    {
        printf_s("v%-5d",i);
    }
    printf_s("\n");
    for(int i = 0;i < 顶点数;i++)
    {
        printf_s("%-6d",顶点[i]);
    }
    printf_s("\n");
    
    printf_s("邻接矩阵：\n");
    //邻接矩阵第一行
    printf_s("%6s","");
    for(int i = 0;i < 顶点数;i++)
    {
        printf_s("v%-5d",i);
    }
    printf_s("\n");
    //邻接矩阵数据行
    for(int i = 0;i < 顶点数;i++)
    {
        printf_s("v%-5d",i);
        for(int j = 0;j < 顶点数;j++)
        {
            printf_s("%-6d",邻接矩阵[i][j]);
        }
        printf_s("\n");
    }
}
